package zzw.sorting;

/**
 * Description:
 * 冒泡排序：它会遍历若干次要排序的数列，每次遍历时，它都会从前往后依次的比较相邻两个数的大小；如果前者比后者大，则交换它们的
 * 位置。这样，一次遍历之后，最大的元素就在数列的末尾！ 采用相同的方法再次遍历时，第二大的元素就被排列在最大元素之前。重复此
 * 操作，直到整个数列都有序为止！
 * 稳定算法。 时间复杂度是O(N2)。
 * @version 1.0
 * @Author zzw
 * @Date: 2018/8/20 11:41
 */
public class BubbleSort {
	public static void main(String[] args) {
		int i;
		int[] a = {20,40,30,10,60,50};
		System.out.printf("before sort:");
		for (i=0; i<a.length; i++) {
			System.out.printf("%d ", a[i]);
		}
		System.out.printf("n");

//		bubbleSort1(a, a.length);
		bubbleSort2(a, a.length);

		System.out.printf("after  sort:");
		for (i=0; i<a.length; i++) {
			System.out.printf("%d ", a[i]);
		}
		System.out.printf("n");
	}

	/**
	 * 冒泡排序
	 * @param arr 待排序数组
	 * @param length 数组长度
	 */
	public static void bubbleSort1(int [] arr,int length){
		int i,j;
		for ( i = length-1; i >0; i--) {
			for (j=0; j<i; j++){
				if(arr[j] > arr[j+1]){
					int temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1]=temp;

				}
			}
		}
	}

	/**
	 * 冒泡排序 改进。某次有序后，不再进行循环
	 * @param arr 待排序数组
	 * @param length 数组长度
	 */
	public static void bubbleSort2(int [] arr,int length){
		int i,j;
		boolean flag = true;
		for ( i = length-1; i >0; i--) {
			for (j=0; j<i; j++){
				if(arr[j] > arr[j+1]){
					int temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1]=temp;
					flag = false;
				}
			}
			if(flag){
				break;
			}
		}
	}
}
